public class 二叉树最大宽度 {
    //https://leetcode.cn/problems/maximum-width-of-binary-tree/description/
    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {}

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public static int HMAX = 2100;
    public static TreeNode[] queue = new TreeNode[HMAX];
    public static int[] nums = new int[HMAX];
    public static int l;
    public static int r;
    public int widthOfBinaryTree(TreeNode root) {
        //添加根节点
        if(root == null){
            return 0;
        }
        //返回值
        int ret = 0;
        l = r = 0;
        //注意r++的使用
        queue[r] = root;
        nums[r++] = 1;
        while(l < r){
            int size = r - l;
            ret = Math.max(ret, nums[r - 1] - nums[l]);
            while(size -- != 0){
                //每次加入的时候把nums也加入了
                TreeNode cur = queue[l];
                if(cur.left != null){
                    queue[r] = cur.left;
                    nums[r] = nums[l] * 2;
                    r++;
                }
                if(cur.right != null){
                    queue[r] = cur.right;
                    nums[r] = nums[l] * 2 + 1;
                    r++;
                }
                l++;
            }
        }
        return ret + 1;
    }

}
